package com.dyz.leetcode._13_binaryTree;

import com.dyz.leetcode.TreeNode;

public class _124_maxPathSum {
    private int maxSum = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }

    private int maxGain(TreeNode node){
        if (node == null) {return 0;}

        // 递归计算左右子节点的最大贡献值
        int leftGain = Math.max(maxGain(node.left), 0);
        int rightGain = Math.max(maxGain(node.right), 0);

        maxSum = Math.max(maxSum, leftGain + rightGain + node.val);

        return Math.max(leftGain, rightGain) + node.val;
    }
}
